/*-
 * Copyright (c) 2012 CTPP Team
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the CTPP Team nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      BPlusTree.tcc
 *
 * $CTPP$
 */

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// B+Tree Template class realization
// For more information see file BPlusTree.hpp
//
//
#include <FTSSException.hpp>
namespace MAIL{



// load from HDD storage to RAM by id 

// if id < 0 - it is leaf
// if id > 0 - it is node
template <typename T, typename V, INT_64 TreeWidth>
inline BPlusNodeType* BPlusTree<T, V, TreeWidth>::getById(INT_64 id, bool bMemClear){
	return cacheHDDStorage->getById(id, bMemClear);
}

// dump node type from RAM to HDD
template <typename T, typename V, INT_64 TreeWidth>
INT_64 BPlusTree<T, V, TreeWidth>::dumpNodeType(BPlusNodeType *pNodeType){
	return cacheHDDStorage->dumpNodeType(pNodeType);
}

// delete node type from HDD
template <typename T, typename V, INT_64 TreeWidth>
void BPlusTree<T, V, TreeWidth>::deleteNodeType(BPlusNodeType *pNodeType){
	cacheHDDStorage->deleteNodeType(pNodeType);
}

//
// Constructor
//
template <typename T, typename V, INT_64 TreeWidth>
 BPlusTree<T, V, TreeWidth>::BPlusTree(
				 CCHAR_P node_storage_name,
				 CCHAR_P node_storage_white_space_name,
				 CCHAR_P leaf_storage_name,
				 CCHAR_P leaf_storage_white_space_name){
	if (TreeWidth < 4) { throw "B+ tree fan-out factor must be at least 4"; }
	// MetaInforamtion for tree
	max_entries = TreeWidth;
	min_entries = max_entries / 2;
	cacheHDDStorage = new FTSS::BPlusCache<T, V, TreeWidth>(node_storage_name,
					 node_storage_white_space_name,
					 leaf_storage_name,
					 leaf_storage_white_space_name);
	// try to restore tree from file
	INT_64 restored_root_id = cacheHDDStorage->restoreRootId();

	// if storages are empty then 
	if (restored_root_id == 0){
		BPlusLeaf <T, V, TreeWidth> *root_node = new BPlusLeaf<T, V, TreeWidth>(0);
		tree_size = 0;
		cacheHDDStorage->dumpRootId(dumpNodeType(root_node));
		cacheHDDStorage->dumpTreeWidth(TreeWidth);
		root = root_node->id;
		//fprintf(stderr, "root_id=%lld\n", root);
		cacheHDDStorage->dumpTreeSize(tree_size);
		dumpNodeType(root_node);
	} else {
		//fprintf(stderr, "restored_roo_id=%lld\n", restored_root_id);
		if (TreeWidth != cacheHDDStorage->restoreTreeWidth()){
			fprintf(stderr, "Tree Width of InvIndex in memory != Tree Width of InvIndex in File\n");
			throw FTSS::LogicException("Tree Width of InvIndex in memory != Tree Width of InvIndex in File");
		}
		root = restored_root_id;
		tree_size = cacheHDDStorage->restoreTreeSize();
		
	}
}

//
// Insert element into tree
//
template <typename T, typename V, INT_64 TreeWidth>
  bool BPlusTree<T, V, TreeWidth>::Insert(const Pair<T, V> & oPair){

	INT_64                     pNewNodeID = 0;
	T                          tValue;

	if (root == 0){ fprintf(stderr, "root=NULL\n"); return false; }
	bool bSplitted = InsertRec(root, oPair, pNewNodeID, tValue, true);

	// split root if neccessary
	if (bSplitted)
	{

		BPlusNode<T, TreeWidth> * pNewRootNode = new BPlusNode<T, TreeWidth>(0);
		dumpNodeType(pNewRootNode);

		pNewRootNode -> children[0] = root;
		BPlusNodeType *zero_children = getById(pNewRootNode -> children[0], false);
		zero_children -> parent = pNewRootNode -> id;
		dumpNodeType(zero_children);

	//	fprintf(stderr, "pNewNodeID=%lld", pNewNodeID);
		pNewRootNode -> children[1] = pNewNodeID;
		BPlusNodeType *first_children = getById(pNewRootNode -> children[1], false);
		first_children -> parent = pNewRootNode -> id;
		dumpNodeType(first_children);

		pNewRootNode -> keys[0] = tValue;
		pNewRootNode -> size = 1;

		dumpNodeType(pNewRootNode);
		root = pNewRootNode -> id;
	//	fprintf(stderr, "pNewRootNode->id=%lld\n", root);
	}
	return true;
}

//
// Recursive insertion
//
template <typename T, typename V, INT_64 TreeWidth>
 bool BPlusTree<T, V, TreeWidth>::InsertRec(INT_64                      pTypeID,
                                            const Pair<T, V>          & oPair,
                                            INT_64                    & pNewTypeID,
                                            T                         & tValue,
					    bool                        first)
{
	BPlusNodeType *pType = getById(pTypeID, first);
	// This is leaf, only insert element
	if (pType -> is_leaf)
	{
		BPlusLeaf<T, V, TreeWidth> * pLeaf = (BPlusLeaf<T, V, TreeWidth> *)(pType);

		// find insertion position
		INT_64 insert_index = SearchLeaf(pLeaf->id, oPair.key);

		// return if entry already exists
		if ((insert_index < pLeaf -> size) && (pLeaf -> pairs[insert_index].key == oPair.key)) {
		//	fprintf(stderr, "already exist I WILL REWRITE IT11111\n");
			pLeaf->pairs[insert_index].value = oPair.value;
			dumpNodeType(pLeaf);
			return false; 
		}
		// insert entry
		for (INT_64 i = pLeaf -> size; i > insert_index; --i) { pLeaf -> pairs[i] = pLeaf -> pairs[i - 1]; }
		pLeaf -> pairs[insert_index] = oPair;
		tree_size++;

		if (pLeaf -> size < max_entries)
		{
			// no need to split, just increment size
			pLeaf -> size++;
			cacheHDDStorage->dumpNodeType(pLeaf);
			return false;
		}
		else
		{
			// must split, so create new node, and copy half of the elements
			BPlusLeaf<T, V, TreeWidth> * pNewLeaf = new BPlusLeaf<T, V, TreeWidth>(pLeaf -> parent);
			dumpNodeType(pNewLeaf);

			insert_index = 0;
			for (INT_64 i = min_entries; i <= max_entries; ++i)
			{
				pNewLeaf -> pairs[insert_index] = pLeaf -> pairs[i];

				// очистка лишних мест зануление пустыми нодами и листьями
				pLeaf -> pairs[i].key = T();pLeaf -> pairs[i].value = V();
				++insert_index;
			}

			// set sizes of each node
			pLeaf -> size    = min_entries;
			pNewLeaf -> size = insert_index;

			// update next pointers of each node
			pNewLeaf -> next = pLeaf -> next;
			pLeaf -> next = pNewLeaf -> id;

			// return the new node and its separator
			pNewTypeID = pNewLeaf->id;
			tValue = pLeaf -> pairs[min_entries - 1].key;
			
			dumpNodeType(pLeaf);
			dumpNodeType(pNewLeaf);
			
			return true;
		}
	}
	// This is node, perform to recursive insertion in a tree
	else
	{
		BPlusNode<T, TreeWidth> * pNode = (BPlusNode<T, TreeWidth> *)(pType);
		INT_64 pInsertNodeID = 0;
		T tInsert;

		// recurse and return immediately if no change propagated up
		bool bSplitted = InsertRec(pNode -> children[SearchNode(pNode->id, oPair.key)], oPair, pInsertNodeID , tInsert, false);
		

		// если я правильно понимаю здесь должен вернуться в pInsertNodeId - id этой ноды и соответственно
		// по нему надо найти ноду на HDD
		BPlusNodeType * pInsertNode = pInsertNodeID != 0 ? getById(pInsertNodeID, false) : NULL;

		if (!bSplitted) { 
			if (pInsertNode != NULL){
				dumpNodeType(pInsertNode);
			}
			dumpNodeType(pNode);
			return false;
		 }

		// insert separator
		INT_64 insert_index = SearchNode(pNode->id, tInsert);

		for (INT_64 i = pNode -> size ; i > insert_index; --i)
		{
			pNode -> keys[i]         = pNode -> keys[i - 1];
			pNode -> children[i + 1] = pNode -> children[i];
		}
		pNode -> keys[insert_index]         = tInsert;
		//fprintf(stderr, "pInsertNodeId=%lld, pInsertNode=%s\n", pInsertNodeID, pInsertNode == NULL ? "NULL" : "NOT NULL" );
		pNode -> children[insert_index + 1] = pInsertNodeID == 0 ? 0 : pInsertNode->id;

		if (pNode -> size < max_entries)
		{
			// no need to split, just increment size
			pNode -> size++;
			dumpNodeType(pInsertNode);
			dumpNodeType(pNode);
			return false;
		} else	{

			// must split, so create new node, a=nd copy half of the elements
			BPlusNode<T, TreeWidth> * pNewNode = new BPlusNode<T, TreeWidth>(pNode -> parent);
			dumpNodeType(pNewNode);
			insert_index = 0;
			for (INT_64 i = min_entries + 1; i <= max_entries; ++i)
			{
				// copy children
				pNewNode -> children[insert_index] = pNode -> children[i];
				BPlusNodeType *children_insert_index = getById(pNewNode -> children[insert_index], false); 
				children_insert_index -> parent = pNewNode -> id ;
				pNode -> children[i] = 0;
				// copy separator
				pNewNode -> keys[insert_index] = pNode -> keys[i];
				// опять зануление проверить что правильно это работает 
				pNode -> keys[i] = T();
				insert_index++;
				dumpNodeType(children_insert_index);
			}
			// copy rightmost child
			pNewNode -> children[insert_index] = pNode -> children[max_entries + 1];
			BPlusNodeType *children_insert_index_2 = getById(pNewNode -> children[insert_index], false);
			children_insert_index_2 -> parent = pNewNode -> id;
 			pNode -> children[max_entries + 1] = 0;

			// set sizes of each node
			pNode -> size = min_entries;
			pNewNode -> size = insert_index;

			// return the new node and its separator
			pNewTypeID = pNewNode->id;
			tValue = pNode -> keys[min_entries];

			// и очередное зануление
			pNode -> keys[min_entries] = T();
			dumpNodeType(pNode);
			dumpNodeType(children_insert_index_2);
			dumpNodeType(pNewNode);
			return true;
		}
	}
	/* This should *NOT* happened. */
	// очень, блять, на это надеюсь 
	return false;
}

	/**
	 * Returns whether the B+ tree contains a value equal to <code>entry</code>.
	 *
	 * @param entry
	 * the value whose presence to check for in the tree
	 * @return <code>true</code> if the B+ tree contains a value equal to
	 * <code>entry</code>, <code>false</code> otherwise
	 */
//template <typename T, typename V, INT_64 TreeWidth>
//  bool BPlusTree<T, V, TreeWidth>::contains(T entry)
//{
//	BPlusNode<T, TreeWidth> * leaf = getLeaf(root, entry);
//	INT_64 find_index = SearchLeaf(leaf, entry);
//	return ((find_index < leaf -> size) && (leaf -> keys[find_index] == entry));
//}

	/*
	 * Returns leaf into which entry can be inserted or found.
	 
	protected BPlusNode getLeaf(BPlusNode node, Comparable entry) {
		if (node.is_leaf) {
			return node;
		}
		return getLeaf(node.children[SearchNode(node, entry)], entry);
	}*/

/*
 * Returns index of first entry greater than or equal to entry. If
 * inserting, this is the index at which entry belongs. If searching, this
 * is the index where entry should be.
 */
template <typename T, typename V, INT_64 TreeWidth>
  INT_64 BPlusTree<T, V, TreeWidth>::SearchLeaf(INT_64 pLeafID, const T & tKey){
	BPlusLeaf<T, V, TreeWidth> *pLeaf = (BPlusLeaf<T, V, TreeWidth> *) getById(pLeafID, false);
	if (pLeaf -> size == 0) {
		 return 0;
	 // little change for kill g++ warning about math
	 // backup string is :
	//}else if (pLeaf -> pairs[pLeaf -> size - 1].key < tKey < 0) {
	}else if ((pLeaf -> pairs[pLeaf -> size - 1].key < tKey) < 0) {
		 return pLeaf -> size; 
	}

	return BisectLeftLeaf(pLeaf->id, tKey, 0, pLeaf -> size);
}

/*
 * Retruns index of the first separator greater than or equal to sep. If
 * inserting, this is the index at which sep belongs. If searching, this is
 * the index of the child to recurse on.
 */
template <typename T, typename V, INT_64 TreeWidth>
  INT_64 BPlusTree<T, V, TreeWidth>::SearchNode(INT_64 pNodeID, const T & tKey){
	BPlusNode<T,TreeWidth> *pNode = (BPlusNode<T,TreeWidth> *)getById(pNodeID, false);
	if (pNode -> keys[pNode -> size - 1] < tKey) { return pNode -> size; }
	return BisectLeftNode(pNode->id, tKey, 0, pNode -> size);
}

template <typename T, typename V, INT_64 TreeWidth>
  INT_64 BPlusTree<T, V, TreeWidth>::BisectLeftLeaf(INT_64                        pLeafID,
                                                    const T                     & tKey,
                                                    INT_64                        iPos,
                                                    const INT_64                  iEndPos)
{

	BPlusLeaf<T, V, TreeWidth> *pLeaf = (BPlusLeaf<T, V, TreeWidth> *)getById(pLeafID, false);	
	for (; iPos < iEndPos; ++iPos){
		if (pLeaf -> pairs[iPos].key >= tKey) {
			 return iPos; 
		}
	}
	return iEndPos;
}

template <typename T, typename V, INT_64 TreeWidth>
  INT_64 BPlusTree<T, V, TreeWidth>::BisectLeftNode(INT_64                      pNodeID,
                                                    const T                    & tKey,
                                                    INT_64                       iPos,
                                                    const INT_64                 iEndPos)

{
	BPlusNode<T, TreeWidth> *pNode = (BPlusNode<T, TreeWidth> *)getById(pNodeID, false);
	for (; iPos < iEndPos; ++iPos){
		if (pNode -> keys[iPos] >= tKey) { 
			return iPos; 
		}
	}

	return iEndPos;
}

/*
	protected INT_64 bisectRight(Comparable[] array, Comparable value, INT_64 _lo, INT_64 _hi) {
		INT_64 lo = (_lo < 0) ? 0 : _lo;
		INT_64 hi = (_hi < 0) ? array.length : _hi;
		while (lo < hi) {
			INT_64 mid = (lo + hi) / 2;
			if (value.compareTo(array[mid]) < 0) {
				hi = mid;
			}
			else {
				lo = mid + 1;
			}
		}
		return lo;
	}
*/
	/**
	 * Returns an array containing all values greater than or equal to the
	 * argument <code>min_entry</code> and less than or equal to the argument
	 * <code>max_entry</code>. The values are returned in ascending order. If
	 * the list fits in the specified array, it is returned therein.
	 * Otherwise, a new array is allocated with the runtime type of
	 * <code>T</code> and the size of this list. If the list fits in the
	 * specified array with room to spare, the element in the array
	 * immediately following the end of the collection is set to
	 * <code>NULL</code>.
	 *
	 * @param min_entry
	 * the lower bound of all values returned
	 * @param max_entry
	 * the upper bound of all values returned
	 * @param _array
	 * the array into which the elements of the list are to be stored, if it
	 * is big enough
	 * @return an array containing all values between <code>min_entry</code>
	 * and <code>max_entry</code>, inclusively
	 */
//template <typename T, typename V, INT_64 TreeWidth>
//  INT_64 BPlusTree<T, V, TreeWidth>::
//T * search(T min_entry, T max_entry, T* _array)
//{
/*	if (max_entry.compareTo(min_entry) < 0)
	{
		throw new IllegalArgumentException("Invalid search range specified");
	}

	// find leaf that min_entry belongs in
	BPlusNode start_node = getLeaf(root, min_entry);
	// then find first value greater than or equal to min_entry
	INT_64 start_index = SearchLeaf(start_node, min_entry);

	// first count number of entries between min_entry and max_entry
	INT_64 num_results = 0;
	BPlusNode curr_node = start_node;
	INT_64 curr_index = start_index;
	while (curr_node != NULL)
	{
		if (curr_node.keys[curr_node.size - 1].compareTo(max_entry) <= 0)
		{
			// all values less than or equal to max_entry
			num_results += (curr_node.size - curr_index);
			curr_node = curr_node.next;
			curr_index = 0;
		}
		else
		{
			// find first value greater than max_entry
			INT_64 gt_index = bisectRight(curr_node.keys, max_entry, curr_index, curr_node.size);
			// add number of values less than or equal to max_entry
			num_results += (gt_index - curr_index);
			break;
		}
	}

	// prepare array to return results
	T[] results = (_array.length >= num_results) ? _array : (T[]) Array.newInstance(_array.getClass().getComponentType(), num_results);
	if (results.length > num_results)
	{
		results[num_results] = NULL;
	}

	if (num_results == 0)
	{
		return results;
	}
	INT_64 next_index = 0;

	// now copy in all entries between min_entry and max_entry, inclusive
	curr_node = start_node;
	curr_index = start_index;
	while (next_index < num_results) {
		if (curr_node.keys[curr_node.size - 1].compareTo(max_entry) <= 0) {
			// all values less than or equal to max_entry
			INT_64 copy_length = curr_node.size - curr_index;
			System.arraycopy(curr_node.keys, curr_index, results,
						next_index, copy_length);
			next_index += copy_length;
			curr_node = curr_node.next;
			curr_index = 0;
		}
		else {
//			// copy until first value greater than max_entry
			System.arraycopy(curr_node.keys, curr_index, results,
					next_index, num_results - next_index);
			break;
		}
	}
	// return all entries
	return results;
*/
//}

	/**
	 * Removes the value equal to <code>entry</code> from the B+ tree. If the
	 * tree does not contain a value equal to <code>entry</code>, meaning
	 * that method <code>contains(entry)</code> returns <code>false</code>,
	 * the tree is unchanged and this method has no effect.
	 *
	 * @param entry
	 * the value to remove from the B+ tree
	 * @return <code>true</code> if a value equal to <code>entry</code> was
	 * found and removed, <code>false</code> otherwise
	 */

template <typename T, typename V, INT_64 TreeWidth>
  bool BPlusTree<T, V, TreeWidth>::Remove(const T & tKey)
{
//	fprintf(stderr, "try to delete with key = <%lld, %lld>\n", ((T &) tKey).iWordHash, ((T &)tKey).iChunkNumber);
	return RemoveRec(root, 0, 0, 0, 0, tKey);
}

template <typename T, typename V, INT_64 TreeWidth>
  bool BPlusTree<T, V, TreeWidth>::RemoveRec(INT_64    pThisTypeID,
                                             INT_64    pLeftTypeID,
                                             INT_64    pRightTypeID,
                                             INT_64    left_anchorID,
                                             INT_64    right_anchorID,
				             const T & entry,
					     bool      first)
{
	BPlusNodeType *pThisType = getById(pThisTypeID);
	// Node
	if (!pThisType -> is_leaf)
	{
		BPlusNodeType *pLeftType = getById(pLeftTypeID);
		BPlusNodeType *pRightType = getById(pRightTypeID);
		
		BPlusNode<T, TreeWidth> * pCurrentNode = (BPlusNode<T, TreeWidth> *)(pThisType);

		BPlusNode<T, TreeWidth> * pLeftNode  = (BPlusNode<T, TreeWidth> *)(pLeftType);
		BPlusNode<T, TreeWidth> * pRightNode = (BPlusNode<T, TreeWidth> *)(pRightType);

		INT_64 child_index = SearchNode(pCurrentNode->id, entry);

//		BPlusNode<T, TreeWidth> * next_node = pCurrentNode -> children[child_index];
		BPlusNodeType * pNextType = getById(pCurrentNode -> children[child_index]);

		// calculate immediate neighbor and their anchor nodes
		BPlusNodeType * next_left = NULL;
		BPlusNodeType * next_right = NULL ;
		BPlusNodeType * next_left_anchor = NULL ;
		BPlusNodeType * next_right_anchor = NULL;

		if (child_index == 0)
		{
			next_left = (pLeftNode != NULL) ? getById(pLeftNode -> children[pLeftNode -> size]) : NULL;
			next_left_anchor = getById(left_anchorID);
		}
		else
		{
			next_left = getById(pCurrentNode -> children[child_index - 1]);
			next_left_anchor = pCurrentNode;
		}

		if (child_index == pCurrentNode -> size)
		{
			next_right = (pRightNode != NULL) ? getById(pRightNode -> children[0]) : NULL;
			next_right_anchor = getById(right_anchorID);
		}
		else
		{
			next_right = getById(pCurrentNode -> children[child_index + 1]);
			next_right_anchor = pCurrentNode;
		}

		// recursively remove on correct child
		bool removed = RemoveRec(pNextType != NULL ? pNextType->id : 0, 
		                         next_left != NULL ? next_left->id : 0, 
					 next_right != NULL ? next_right->id : 0, 
					 next_left_anchor != NULL ? next_left_anchor->id : 0, 
					 next_right_anchor != NULL ? next_right_anchor->id : 0, 
					 entry);
		
		if (pCurrentNode->id == root)
		{
			// if root collapsed to a single child, make child new root
			if (pCurrentNode -> size == 0)
			{
				root = pCurrentNode -> children[0];
				BPlusNodeType *root_node = getById(root, false);
				root_node -> parent = 0;
				dumpNodeType(root_node);
			}
		}
		else if (pCurrentNode -> size < min_entries)
		{
			// assign largest immediate neighbor to max_neighbor
			BPlusNode<T, TreeWidth> * max_neighbor = (pLeftNode != NULL) ? pLeftNode : pRightNode;
			if ((pRightNode != NULL) && (pRightNode -> size > max_neighbor -> size))
			{
				max_neighbor = pRightNode;
			}

			if (max_neighbor -> size > min_entries)
			{
				// borrow from neighbor node found with most entries
				if (max_neighbor == pLeftNode)
				{
					BPlusNodeType *left_anchor = getById(left_anchorID);
					BPlusNode<T, TreeWidth> * pLeftAhchor = (BPlusNode<T, TreeWidth> *)(left_anchor);
					ShiftNodes(pCurrentNode->id, pLeftNode->id, pLeftAhchor->id, false);
				}
				else
				{
					BPlusNodeType *right_anchor = getById(right_anchorID);
					BPlusNode<T, TreeWidth> * pRightAhchor = (BPlusNode<T, TreeWidth> *)(right_anchor);
					ShiftNodes(pCurrentNode->id, pRightNode->id, pRightAhchor->id, true);
				}
			}
			else
			{
				// merge with immediate neighbor
				BPlusNodeType *left_anchor = getById(left_anchorID);
				if (pCurrentNode -> parent == left_anchor -> id)
				{
					BPlusNode<T, TreeWidth> * pLeftAhchor = (BPlusNode<T, TreeWidth> *)(left_anchor);
					MergeNodes(pLeftNode->id, pCurrentNode->id, pLeftAhchor->id);
				}
				else
				{
					BPlusNodeType *right_anchor = getById(right_anchorID);
					BPlusNode<T, TreeWidth> * pRightAhchor = (BPlusNode<T, TreeWidth> *)(right_anchor);
					MergeNodes(pCurrentNode->id, pRightNode->id, pRightAhchor->id);
				}
			}
		}

		// возможно дампятся лишние ( можно оптимизировать )
		//dumpNodeType(pCurrentNode);
		////dumpNodeType(pLeftNode);
		////dumpNodeType(pRightNode);
		//dumpNodeType(pNextType);
		//dumpNodeType(next_left);
		//dumpNodeType(next_right);
		//dumpNodeType(next_right_anchor);
		//dumpNodeType(next_left_anchor);
		return removed;
	}
	// Leaf
	else
	{
		BPlusNodeType *pLeftType = getById(pLeftTypeID);
		BPlusNodeType *pRightType = getById(pRightTypeID);
		BPlusLeaf<T, V, TreeWidth> * pCurrentNode = (BPlusLeaf<T, V, TreeWidth> *)(pThisType);
		BPlusLeaf<T, V, TreeWidth> * pLeftNode  = (BPlusLeaf<T, V, TreeWidth> *)(pLeftType);
		BPlusLeaf<T, V, TreeWidth> * pRightNode = (BPlusLeaf<T, V, TreeWidth> *)(pRightType);

//			fprintf(stderr, "HERE, pCurrent_node=%lld\n", pCurrentNode->id);
		// find deletion position
		INT_64 delete_index = SearchLeaf(pCurrentNode->id, entry);
		// return false if entry does not exist
		if ((delete_index >= pCurrentNode -> size) || (pCurrentNode -> pairs[delete_index].key != entry)){
			return false;
		}

		// delete value
		for (INT_64 i = delete_index + 1; i < pCurrentNode -> size; ++i)
		{
			pCurrentNode -> pairs[i - 1] = pCurrentNode -> pairs[i];
		}
//		fprintf(stderr, "pCurrentNode->size=%lld\n", pCurrentNode->size);
		pCurrentNode -> size --;
//		fprintf(stderr, "pCurrentNode->size=%lld\n", );
		tree_size --;
		// зануление очередное

		if ((pCurrentNode->id != root) && (pCurrentNode -> size < min_entries))
		{
			// assign largest immediate neighbor to max_neighbor
			BPlusLeaf<T, V, TreeWidth> * max_neighbor = (pLeftNode != NULL) ? pLeftNode : pRightNode;

			if ((pRightNode != NULL) && (pRightNode -> size > max_neighbor -> size))
			{
				max_neighbor = pRightNode;
			}

			if (max_neighbor -> size > min_entries)
			{
				// borrow from neighbor node found with most entries
				if (max_neighbor == pLeftNode)
				{
					BPlusNodeType *left_anchor = getById(left_anchorID);
					BPlusNode<T, TreeWidth> * pLeftAhchor = (BPlusNode<T, TreeWidth> *)(left_anchor);
					ShiftLeafs(pCurrentNode->id, pLeftNode->id, pLeftAhchor->id, false);
				}
				else
				{
					BPlusNodeType *right_anchor = getById(right_anchorID);
					BPlusNode<T, TreeWidth> * pRightAhchor = (BPlusNode<T, TreeWidth> *)(right_anchor);
					ShiftLeafs(pCurrentNode->id, pRightNode->id, pRightAhchor->id, true);
				}
			}
			else
			{
				// merge with immediate neighbor
				BPlusNodeType *left_anchor = getById(left_anchorID);
				if (pCurrentNode -> parent == left_anchor -> id)
				{
					BPlusNode<T, TreeWidth> * pLeftAhchor = (BPlusNode<T, TreeWidth> *)(left_anchor);
					MergeLeafs(pLeftNode->id, pCurrentNode->id, pLeftAhchor->id);
				}
				else
				{
					BPlusNodeType *right_anchor = getById(right_anchorID);
					BPlusNode<T, TreeWidth> * pRightAhchor = (BPlusNode<T, TreeWidth> *)(right_anchor);
					MergeLeafs(pCurrentNode->id, pRightNode->id, pRightAhchor->id);
				}
			}
		}
		dumpNodeType(pLeftNode);
		dumpNodeType(pRightNode);
		dumpNodeType(pCurrentNode);
		return true;
	}
	/* This should *NOT* happened. */
	return false;
}

template <typename T, typename V, INT_64 TreeWidth>
  void BPlusTree<T, V, TreeWidth>::ShiftLeafs(INT_64 pCurrentNodeID,
  					      INT_64 neighbor_nodeID,
					      INT_64 anchor_nodeID,
					      bool   copy_from_right)
{
	BPlusLeaf<T, V, TreeWidth> *neighbor_node = (BPlusLeaf<T, V, TreeWidth> *)getById(neighbor_nodeID);
	BPlusLeaf<T, V, TreeWidth> *pCurrentNode = (BPlusLeaf<T, V, TreeWidth> *)getById(pCurrentNodeID);
	// determine number of values to copy
	INT_64 num_copy = (neighbor_node -> size + 1 - pCurrentNode -> size) / 2;

	// новые элемент = -1, почему -1 - хз, попробуем вызывать дефолтный конструктор
	//T prev_sep = -1;
	//T new_sep = -1;
	T prev_sep = T();
	T new_sep = T();
	if (copy_from_right)
	{
		// copy values from neighbor_node on right to pCurrentNode
		for (INT_64 i = 0; i < num_copy; ++i)
		{
			pCurrentNode -> pairs[pCurrentNode -> size + i] = neighbor_node -> pairs[i];
		}
		// now shift values in neighbor_node
		for (INT_64 i = 0; i < neighbor_node -> size - num_copy; ++i)
		{
			neighbor_node -> pairs[i] = neighbor_node -> pairs[i + num_copy];
		}
		for (INT_64 i = neighbor_node -> size - num_copy; i < neighbor_node -> size; ++i)
		{
			neighbor_node -> pairs[i].key = T();
			// надеюсь что все таки value
			neighbor_node -> pairs[i].value = V();
		}
		// set the potential old separator and the new separator
		prev_sep = pCurrentNode -> pairs[pCurrentNode -> size - 1].key;
		new_sep = pCurrentNode -> pairs[pCurrentNode -> size + num_copy - 1].key;
	}
	else
	{
		// shift values in pCurrentNode
		for (INT_64 i = pCurrentNode -> size - 1; i >= 0; --i)
		{
			pCurrentNode -> pairs[i + num_copy] = pCurrentNode -> pairs[i];
		}
		// copy values from neighbor_node on left to pCurrentNode
		for (INT_64 i = 0; i < num_copy; ++i)
		{
			pCurrentNode -> pairs[i] = neighbor_node -> pairs[neighbor_node -> size - num_copy + i];
			// зануление снова
			neighbor_node -> pairs[neighbor_node -> size - num_copy + i].key = T();
			neighbor_node -> pairs[neighbor_node -> size - num_copy + i].value = V();
		}
		// set the potential old separator and the new separator
		prev_sep = pCurrentNode -> pairs[num_copy - 1].key;
		new_sep = neighbor_node -> pairs[neighbor_node -> size - num_copy - 1].key;
	}
	// adjust sizes
	pCurrentNode -> size += num_copy;
	neighbor_node -> size -= num_copy;

	BPlusNode<T, TreeWidth> *anchor_node = (BPlusNode<T, TreeWidth> *)getById(anchor_nodeID);
	// replace separator in anchor
	anchor_node -> keys[SearchNode(anchor_node->id, prev_sep)] = new_sep;
	dumpNodeType(anchor_node);
	dumpNodeType(pCurrentNode);
	dumpNodeType(neighbor_node);
}

template <typename T, typename V, INT_64 TreeWidth>
  void BPlusTree<T, V, TreeWidth>::ShiftNodes(INT_64 pThisNodeID,
  					      INT_64 pSiblingID,
 				              INT_64 pParentNodeID,
				              bool copy_from_right)
{
	BPlusNode<T, TreeWidth> *pThisNode = (BPlusNode<T, TreeWidth> *)getById(pThisNodeID);
	BPlusNode<T, TreeWidth> *pSibling =  (BPlusNode<T, TreeWidth> *)getById(pSiblingID);
	// determine number of separators to copy
	INT_64 num_copy = (pSibling -> size + 1 - pThisNode -> size) / 2;

	if (copy_from_right)
	{
		BPlusNode<T, TreeWidth> *pParentNode = (BPlusNode<T, TreeWidth> *)getById(pParentNodeID);
		// copy down separator from pParentNode to pThisNode
		INT_64 sep_pos = SearchNode(pParentNode->id, pThisNode -> keys[pThisNode -> size - 1]);
		pThisNode -> keys[pThisNode -> size] = pParentNode -> keys[sep_pos];
		// copy up new separator from pSibling to pParentNode
		pParentNode -> keys[sep_pos] = pSibling -> keys[num_copy - 1];
		// copy separators and children from pSibling on right to pThisNode
		for (INT_64 i = 0; i < num_copy - 1; ++i)
		{
			pThisNode -> keys[pThisNode -> size + 1 + i] = pSibling -> keys[i];
			pThisNode -> children[pThisNode -> size + 1 + i] = pSibling -> children[i];
			//pThisNode -> children[pThisNode -> size + 1 + i] -> parent = pThisNode -> i -> idd;
			BPlusNodeType *child = getById(pThisNode -> children[pThisNode -> size + 1 + i]);
			child -> parent = pThisNode -> id;
			dumpNodeType(child);
		}
		pThisNode -> children[pThisNode -> size + num_copy] = pSibling -> children[num_copy - 1];
		BPlusNodeType *childer = getById(pThisNode -> children[pThisNode -> size + num_copy]);
		childer -> parent = pThisNode -> id;
		dumpNodeType(childer);
		// shift separators and children in pSibling
		for (INT_64 i = 0; i < pSibling -> size - num_copy; ++i)
		{
			pSibling -> keys[i] = pSibling -> keys[i + num_copy];
			pSibling -> children[i] = pSibling -> children[i + num_copy];
		}
		pSibling -> children[pSibling -> size - num_copy] = pSibling -> children[pSibling -> size];
		for (INT_64 i = pSibling -> size - num_copy; i < pSibling -> size; ++i)
		{
			// зануление
			pSibling -> keys[i] = T();
			pSibling -> children[i + 1] = 0;
		}
	}
	else
	{
		BPlusNode<T, TreeWidth> *pParentNode = (BPlusNode<T, TreeWidth> *)getById(pParentNodeID);
		// shift separators and children in pThisNode
		pThisNode -> children[pThisNode -> size + num_copy] = pThisNode -> children[pThisNode -> size];
		for (INT_64 i = pThisNode -> size - 1; i >= 0; --i)
		{
			pThisNode -> keys[i + num_copy] = pThisNode -> keys[i];
			pThisNode -> children[i + num_copy] = pThisNode -> children[i];
		}
		// copy down separator from pParentNode to pThisNode
		INT_64 sep_pos = SearchNode(pParentNode->id, pSibling -> keys[pSibling -> size - 1]);
		pThisNode -> keys[num_copy - 1] = pParentNode -> keys[sep_pos];
		// copy up new separator from pSibling to pParentNode
		pParentNode -> keys[sep_pos] = pSibling -> keys[pSibling -> size - num_copy];
		//зануление
		pSibling -> keys[pSibling -> size - num_copy] = T();
		// copy separators and children from pSibling on left to pThisNode
		for (INT_64 i = 0; i < num_copy - 1; ++i)
		{
			pThisNode -> keys[i] = pSibling -> keys[pSibling -> size + 1 - num_copy + i];
			// зануление
			pSibling -> keys[pSibling -> size + 1 - num_copy + i] = T();
			pThisNode -> children[i] = pSibling -> children[pSibling -> size + 1 - num_copy + i];
			pSibling -> children[pSibling -> size + 1 - num_copy + i] = 0;
			BPlusNodeType *cchild = getById(pThisNode -> children[i]);
			cchild -> parent = pThisNode -> id;
			dumpNodeType(cchild);
		}
		pThisNode -> children[num_copy - 1] = pSibling -> children[pSibling -> size];
		pSibling -> children[pSibling -> size] = 0;
		BPlusNodeType * ch = getById(pThisNode -> children[num_copy - 1]);
		ch -> parent = pThisNode -> id;
		dumpNodeType(ch);
		dumpNodeType(pParentNode);
	}
	// adjust sizes
	pThisNode -> size += num_copy;
	pSibling -> size -= num_copy;
	dumpNodeType(pSibling);
	dumpNodeType(pThisNode);
}

/**
  @brief Merge two leafs
  @param pLeftNode - left leaf
  @param pRightNode - right leaf
  @param pParentNode - parent node
*/
// похоже умирает правый лист
template <typename T, typename V, INT_64 TreeWidth>
  void BPlusTree<T, V, TreeWidth>::MergeLeafs(INT_64 pLeftNodeID,
                                              INT_64 pRightNodeID,
                                              INT_64 pParentNodeID)
{
	BPlusLeaf<T, V, TreeWidth> *pLeftNode = (BPlusLeaf<T, V, TreeWidth> *)getById(pLeftNodeID);
	BPlusLeaf<T, V, TreeWidth> *pRightNode = (BPlusLeaf<T, V, TreeWidth> *)getById(pRightNodeID);
	BPlusNode<T, TreeWidth> *pParentNode = (BPlusNode<T, TreeWidth> *)getById(pParentNodeID);
	INT_64 sep_pos = SearchNode(pParentNode->id, pLeftNode -> pairs[pLeftNode -> size - 1].key);
	// shift all separators and children beyond its right child
	for (INT_64 i = sep_pos + 1; i < pParentNode -> size; ++i)
	{
		pParentNode -> keys[i - 1] = pParentNode -> keys[i];
		pParentNode -> children[i] = pParentNode -> children[i + 1];
	}
	// зануление опять
	pParentNode -> keys[pParentNode -> size - 1] = T();
	pParentNode -> children[pParentNode -> size] = 0;
	// copy values from neighbor_node on right to pCurrentNode
	for (INT_64 i = 0; i < pRightNode -> size; ++i)
	{
		pLeftNode -> pairs[pLeftNode -> size + i] = pRightNode -> pairs[i];
	}
	// adjust size of parent_node and pLeftNode
	pLeftNode -> size += pRightNode -> size;
	pParentNode -> size --;
	// update next pointer
	pLeftNode -> next = pRightNode -> next;
	// sync with hdd
	dumpNodeType(pParentNode);
	// вроде правый лист погибает
	deleteNodeType(pRightNode);
	//dumpNodeType(pRightNode);
	dumpNodeType(pLeftNode);
}


/**
  @brief Merge two nodes
  @param pLeftNode - left node
  @param pRightNode - right node
  @param pParentNode - parent node
*/
template <typename T, typename V, INT_64 TreeWidth>
  void BPlusTree<T, V, TreeWidth>::MergeNodes(INT_64 pLeftNodeID,
				              INT_64 pRightNodeID,
				              INT_64 pParentNodeID)
{
	BPlusNode<T, TreeWidth> *pLeftNode = (BPlusNode<T, TreeWidth> *)getById(pLeftNodeID);
	BPlusNode<T, TreeWidth> *pRightNode = (BPlusNode<T, TreeWidth> *)getById(pRightNodeID);
	BPlusNode<T, TreeWidth> *pParentNode = (BPlusNode<T, TreeWidth> *)getById(pParentNodeID);
	// copy separator from parent node
	INT_64 sep_pos = SearchNode(pParentNode->id, pLeftNode -> keys[pLeftNode -> size - 1]);

	pLeftNode -> keys[pLeftNode -> size] = pParentNode -> keys[sep_pos];

	// to remove, shift all separators and children beyond its right child
	for (INT_64 i = sep_pos + 1; i < pParentNode -> size; ++i)
	{
		pParentNode -> keys[i - 1] = pParentNode -> keys[i];
		pParentNode -> children[i] = pParentNode -> children[i + 1];
	}
	// обнуление key
	pParentNode -> keys[pParentNode -> size - 1] = T();
	pParentNode -> children[pParentNode -> size] = 0;

	// increment size of pLeftNode now that separator is copied
	pLeftNode -> size ++;
	// copy separators and children from neighbor_node on right to pCurrentNode
	for (INT_64 i = 0; i < pRightNode -> size; ++i)
	{
		pLeftNode -> keys[pLeftNode -> size + i]     = pRightNode -> keys[i];
		pLeftNode -> children[pLeftNode -> size + i] = pRightNode -> children[i];
		BPlusNodeType *children = getById(pLeftNode -> children[pLeftNode -> size + i] );
		children -> parent = pLeftNode -> id;
		dumpNodeType(children);
	}
	pLeftNode -> children[pLeftNode -> size + pRightNode -> size] = pRightNode -> children[pRightNode -> size];
	BPlusNodeType *pChildren = getById(pLeftNode -> children[pLeftNode -> size + pRightNode -> size]);
	pChildren -> parent = pLeftNode -> id;
	dumpNodeType(pChildren);

	// adjust size of parent_node and pLeftNode
	pLeftNode -> size += pRightNode -> size;
	pParentNode -> size -- ;

	// sync with hdd
	dumpNodeType(pLeftNode);
	// вроде тоже правая нода умирает
	//dumpNodeType(pRightNode);
	deleteNodeType(pRightNode);
	dumpNodeType(pParentNode);
}


template <typename T, typename V, INT_64 TreeWidth>
 BPlusTree<T, V, TreeWidth>::~BPlusTree(){
	cacheHDDStorage->dumpRootId(root);
	cacheHDDStorage->dumpTreeSize(tree_size);
	delete cacheHDDStorage;
 }

template <typename T, typename V, INT_64 TreeWidth>
void BPlusTree<T, V, TreeWidth>::DFSPrintTree(){
	fprintf(stderr, "TREE:, root=%lld\n", root);
	DFSPrintTreeRec(root, true);
 }

template <typename T, typename V, INT_64 TreeWidth>
void BPlusTree<T, V, TreeWidth>::DFSPrintTreeRec(INT_64 current_node, bool first){
	fprintf(stderr, "current_node-%lld\n", current_node);
	BPlusNodeType *pCurr = getById(current_node, first);
	fprintf(stderr, "current_node-%lld, pCurr==%s\n", current_node,
	pCurr == NULL ? "NULL" : "NOTNULL");
	if (pCurr->is_leaf){
		BPlusLeaf<T, V, TreeWidth> *pCurrent = (BPlusLeaf<T, V, TreeWidth> *)pCurr;
		fprintf(stderr, "leaf#%lld =[", pCurrent->id);
		for (INT_32 i = 0; i < pCurrent->size; ++i){
			fprintf(stderr, "(key=<%lld,%lld, max_chunk_num=%lld>;value=<%s>)",
							(pCurrent->pairs[i].key).iWordHash,
							(pCurrent->pairs[i].key).iChunkNumber,
							 (pCurrent->pairs[i].key).iSize,
							 (pCurrent->pairs[i].value).pData);
		}
		fprintf(stderr, "],next_id=%lld\n", pCurrent->next);
	} else {
		BPlusNode<T, TreeWidth> *pCurrent = (BPlusNode<T, TreeWidth> *) pCurr;
		fprintf(stderr, "node#%lld =[ ", pCurr->id);
		for (INT_32 i = 0; i < pCurrent->size; ++i){
			fprintf(stderr, "<%lld,%lld>;",(pCurrent->keys[i]).iWordHash
						      ,(pCurrent->keys[i]).iChunkNumber);
		}
		fprintf(stderr, "]\n");
		for (INT_32 i = 0; i <= pCurrent->size; ++i){
			DFSPrintTreeRec(pCurrent->children[i], false);
		}
	}
 }

template <typename T, typename V, INT_64 TreeWidth>
STLW::vector<V*> *BPlusTree<T, V, TreeWidth>::search(T min_entry, T max_entry){
	STLW::vector<V*> *result = new STLW::vector<V*>();
	if (max_entry < min_entry) 
		return result;
	BPlusLeaf<T, V, TreeWidth> *start_leaf = (BPlusLeaf<T, V, TreeWidth> *)getLeaf(root, min_entry);	
	if (start_leaf == NULL) 
		return result;
	BPlusLeaf<T, V, TreeWidth> *current_leaf = start_leaf;
	Pair<T, V> *current_pair = &(start_leaf->pairs[0]);
	INT_32 current_index = 0;
	while (current_pair->key <= max_entry){
		if (current_pair->key >= min_entry && current_pair->key <= max_entry){
			V * pAdd = &(current_pair->value);
			//fprintf(stderr, " adding %s\n", pAdd->data);
			result->push_back(pAdd);
		}
		if (current_index >= current_leaf->size){
			current_index = -1;
			if (current_leaf->next == 0) break;
			else current_leaf = (BPlusLeaf<T, V, TreeWidth> *)getById(current_leaf->next, false);
		}
		++current_index;
		current_pair = &(current_leaf->pairs[current_index]);

	}
	return result;
}


template <typename T, typename V, INT_64 TreeWidth>
CHAR_P BPlusTree<T, V, TreeWidth>::search_array(T min_entry, T max_entry, INT_32 max_size, INT_32 &docEntrySize){
//	fprintf(stderr, "search_array\n");
	INT_32 current_entry = 0;
	INT_32 current_offset = 0;
	CHAR_8 *result = new CHAR_8[max_size * V::getSizeData()];
	if (max_entry < min_entry){ 
		return result;
	}
	BPlusLeaf<T, V, TreeWidth> *start_leaf = (BPlusLeaf<T, V, TreeWidth> *)getLeaf(root, min_entry);	
	if (start_leaf == NULL) 
		return result;
	BPlusLeaf<T, V, TreeWidth> *current_leaf = start_leaf;
	Pair<T, V> *current_pair = &(start_leaf->pairs[0]);
	INT_32 current_index = 0;
	while (current_pair->key <= max_entry){
		if (current_entry >= max_size) { docEntrySize = current_offset; return result;}
		if (current_pair->key >= min_entry && current_pair->key <= max_entry){
			V * pAdd = &(current_pair->value);
			//fprintf(stderr, " adding %s\n", pAdd->data);
			//result->push_back(pAdd);
			memcpy (result + current_offset, pAdd->pData, pAdd->iDataSize);
			current_offset += pAdd->iDataSize;
			++current_entry;
//			fprintf(stderr, "current_offset = %d, pAdd->data_size=%d", current_offset, pAdd->data_size);
		}
		if (current_index >= current_leaf->size){
			current_index = -1;
			if (current_leaf->next == 0) break;
			else {
				current_leaf = (BPlusLeaf<T, V, TreeWidth> *)getById(current_leaf->next, false);
			}
		}
		++current_index;
		current_pair = &(current_leaf->pairs[current_index]);

	}
	docEntrySize = current_offset;
	return result;
}

// находит в дереве нужный элемент и увеличивает
// его значение size на 1 если size_in == true
// или увеличивает значение document_entries на если size_in == false;
template <typename T, typename V, INT_64 TreeWidth>
void BPlusTree<T, V, TreeWidth>::search_and_increment_and_add_DF(const T &entry){
	BPlusLeaf<T, V, TreeWidth> *start_leaf = (BPlusLeaf<T, V, TreeWidth> *)getLeaf(root, entry);
	if (start_leaf == NULL) return;
	Pair<T,V> *current_pair = &(start_leaf->pairs[0]);
	INT_32 current_index = 0;
	while (current_pair-> key != entry && current_index <= start_leaf->size){
		++current_index;
		current_pair = &(start_leaf->pairs[current_index]);
	}
	if (current_pair->key == entry){
			current_pair->key.iDF += entry.iDF;
			++(current_pair->key.iSize);
	}
	dumpNodeType(start_leaf);

}

// возвращает -1 если нет элемента
// возвращает iDF если элемент есть
template <typename T, typename V, INT_64 TreeWidth>
INT_64 BPlusTree<T, V, TreeWidth>::getIDF(T entry){
	BPlusLeaf<T, V, TreeWidth> *start_leaf = (BPlusLeaf<T, V, TreeWidth> *)getLeaf(root, entry);
	if (start_leaf == NULL) return -1;
	Pair<T,V> *current_pair = &(start_leaf->pairs[0]);
	INT_32 current_index = 0;
	while (current_pair-> key != entry && current_index <= start_leaf->size){
		++current_index;
		current_pair = &(start_leaf->pairs[current_index]);
	}
	if (current_pair->key == entry)
		return current_pair->key.iDF;
	return -1;
}

// возвращает -1 если нет элемента
// возвращает size если элемент есть
template <typename T, typename V, INT_64 TreeWidth>
INT_64 BPlusTree<T, V, TreeWidth>::contains(const T & entry){
	BPlusLeaf<T, V, TreeWidth> *start_leaf = (BPlusLeaf<T, V, TreeWidth> *)getLeaf(root, entry);
	if (start_leaf == NULL) return -1;
	Pair<T,V> *current_pair = &(start_leaf->pairs[0]);
	INT_32 current_index = 0;
	while (current_pair-> key != entry && current_index <= start_leaf->size){
		++current_index;
		current_pair = &(start_leaf->pairs[current_index]);
	}
	if (current_pair->key == entry){
		return current_pair->key.iSize;
	}
	return -1;
}

template <typename T, typename V, INT_64 TreeWidth>
BPlusNodeType * BPlusTree<T, V, TreeWidth>::getLeaf(INT_64 node_id, T entry){
	if (node_id == 0) {
		return NULL;
	}
	BPlusNodeType *node = getById(node_id, false);
	if (node == NULL) {
		return NULL;
	}
	if (node->is_leaf){
		return node;
	}
	BPlusNode<T, TreeWidth> *n = (BPlusNode<T, TreeWidth> *)node;
	return getLeaf(n->children[SearchNode(node->id, entry)], entry);
}
} // namespace DSS
// End.
